package com.llb666.java.leetcode;

/**
 * X 为正整数
 * @author 斌~
 * @version 1.0
 * @date 2021/4/25 下午10:59
 */
public class X平方根的整数 {
    public static void main(String[] args) {
        System.out.println(binarySearch(25));
        System.out.println(binarySearch2(25));
    }

    /**
     * 二分法
     * @param x 正整数
     * @return X平方根的整数部分
     */
    private static int binarySearch(int x) {
        int index =-1,left =0,right =x;
        while (left <= right){
            int mid =  left + (right-left)/2;
            if(mid * mid <=x){
                index =mid;
                left =mid +1;
            }else {
                right = mid -1;
            }
        }
        return index;
    }


    /**
     * 牛顿迭代: x = n*n  n = x/n   递归查找n 和 x/n 的中间值
     * @param x 正整数
     * @return X平方根的整数部分
     */
    private static int binarySearch2(int x) {
        if(x== 0){
            return 0;
        }
        return (int)sqrt(x,x);
    }

    public static double sqrt(double i,int x){
        double res = (i+x/i)/2;
        if(res == i ){
            return i;
        }else {
            return sqrt(res,x);
        }
    }
}
